package BTree;

import java.util.Arrays;
import java.util.Random;

public class BTree {
    private static class BTreeNode {
        BTreeNode[] nodes;//储存子节点
        BTreeNode parent;

        int[] vals;//储存数据
        int size = 0;//是数组的有效元素的个数

        public BTreeNode(int M) {
            vals = new int[M];
            nodes = new BTreeNode[M + 1];
            size = 0;
        }
    }

    private BTreeNode root;//这是根
    private int size;//总的元素的个数
    private int M;

    public BTree(int M) {
        root = new BTreeNode(M);//默认都为3
        size = 0;
        this.M = M;
    }

    public Boolean insert(int val) {
        //要先找到要出入的位置
        pair<BTreeNode, Integer> ret = find(val);
        if (ret.getV() == 1) {
            //存在这个val不能插入
            return false;
        }

        //获得插入数据的节点
        BTreeNode cur = ret.getK();
        //插入数据 升序
        insertVal(cur, val);
        size++;cur.size++;

        if (cur.size == M) {
            //这个节点的数组满了 那么就要把他分裂
            spilt(cur);
        }
        return true;
    }

    private void spilt(BTreeNode node) {//完成spilt
        //将mid后面的数据放入新的节点中去
        BTreeNode newNode = new BTreeNode(M);
        int mid = node.vals.length>>1;//右移也就是除二
        int index = 0;//遍历数组

        //数据拷贝
        int i = mid + 1;
        for (; i < node.size; i++) {
            newNode.vals[index] = node.vals[i];//将对应的数据搬运到新的节点
            newNode.nodes[index++] = node.nodes[i];//数据对应的节点搬动新节点
            if(node.nodes[i]!= null)//孩子的父节点移动了，需要跟该对饮的父节点
                node.nodes[i].parent = newNode;
            newNode.size++;
        }
        newNode.nodes[index] = node.nodes[i];//节点比数据多了一个
        if(node.nodes[i]!= null)
            node.nodes[i].parent = newNode;
        newNode.parent = node.parent;//指向同一个父节点
        node.size = node.size - index - 1;//再减去一就是吧mid这数据再给减去了

        //将mid赋给parent并且吧对应的node节点给移动位置
        int mid_val = node.vals[mid];
        BTreeNode parent = node.parent;
        //还有就是node最开始就为root,这是需要单独考虑
        if (parent == null) {
            BTreeNode root = new BTreeNode(M);//创建的新的根节点
            //给root节点赋值
            root.vals[0] = node.vals[mid];
            root.nodes[0] = node;
            root.nodes[1] = newNode;

            //更改子节点的指向
            node.parent = root;
            newNode.parent = root;
            this.root = root;//赋值新的根
            root.size++;
            return;
        }
        //把parent中的数组和节点对应的位置腾空
        int j = 0;
        for (; j < parent.size; j++) {
            //找到对应的插入位置
            if (parent.vals[j] > mid_val) {
                break;
            }
        }
        //插入val再j
        i = parent.size - 1;
        for (; i >= j; i--) {//将parent的val node节点往后移动
            parent.vals[i + 1] = parent.vals[i];
            parent.nodes[i + 2] = parent.nodes[i + 1];
        }
        //插入该值
        parent.vals[i + 1] = mid_val;//因为这是i出循环后已经不等于j 而我们要插入的位置就是j
        parent.nodes[i + 2] = newNode;//而指定的节点位置还比要插入数据的位置大一
        parent.size++;

        if (parent.size == M) {
            spilt(parent);//如果parent加入之后又满了，那么就需要再次去分裂
        }
    }


    private void insertVal(BTreeNode cur, int val) {
       int i = 0;
        for (; i < cur.size; i++) {
            if (val < cur.vals[i]) {
                break;
            }
        }
        for (int j = cur.size - 1; j >= i; j--) {
            cur.vals[j + 1] = cur.vals[j];
        }
        cur.vals[i] = val;
    }

    //返回一个类pair，如果v为-1说明没有这个节点，可以添加，为1就存在不能添加
    BTreeNode parent;//储存父节点
    public pair<BTreeNode, Integer> find(int val) {
        //找到指定的节点
        BTreeNode cur = root;
        while (cur != null) {
            int j = 0;
            //遍历cur的val数组，找到合适的位置
            for (; j < cur.size; j++) {
                if (val < cur.vals[j]) {//小于那么就往下走 大于继续遍历
                    //走到nodes数组的j这个位置
                    break;
                } else if (val == cur.vals[j]) {
                    //等于说明存在这个节点，直接返回这个节点和1
                    return new pair<BTreeNode, Integer>(cur, 1);
                }
            }
            //要放在外面不然如果val大于数组的所有的值那么就会死循环
            parent = cur;
            cur = cur.nodes[j];
        }
        return new pair<BTreeNode, Integer>(parent, -1);
    }

    int[] ValsArray = new int[200];
    int INDEX_ValsArray = 0;//遍历数组
    public void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.size; ++i){
            inorder(root.nodes[i]);
            System.out.print(root.vals[i]+"  ");
            ValsArray[INDEX_ValsArray++] = root.vals[i];
        }
        inorder(root.nodes[root.size]);
    }

    public BTreeNode getRoot() {
        return root;
    }

    public int[] getVals() {
        return ValsArray;
    }
}

class text{
    public static void main(String[] args) {
        BTree hh = new BTree(3);
        int[] arr = {53, 139, 75, 49, 145, 36, 101};
        Random random = new Random();
//        for (int i = 0; i < arr.length; i++) {
//            hh.insert(arr[i]);//子节点再拷贝指向错误 吧拷贝过来的节点的parent指向跟该就好 成功！！！
//        }
//        for (int i = 1; i <= 130; i++) {
//            hh.insert(i);
//        }
        for (int i = 0; i < 200; i++) {
//            hh.insert(random.nextInt(1000));
            hh.insert(1000 - i);
        }
        hh.inorder(hh.getRoot());
        int[] arrr = hh.ValsArray;
        int[] text = {1, 2, 3, 4};
        System.out.println();
        System.out.println(isOrder(arrr));
        
//        System.out.println("stop");
//        hh.inorder(hh.getRoot());
    }

    static boolean isOrder(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            if (Math.abs(arr[i + 1] - arr[i]) != 1) {
                return false;
            }
        }
        return true;
    }
}









